// 堆排序 https://blog.csdn.net/rxbook/article/details/130996393
package main

import "fmt"

// 堆排序,数据由小到大排序,数组下标从1开始
func HeapSort(a []int) {
	length := len(a) - 1
	buidHeap(a, length)
	k := length
	for k >= 1 {
		swap(a, 1, k)
		heapifyUpToDown(a, 1, k-1)
		k--
	}
}

// 构建堆
func buidHeap(a []int, n int) {
	// 从后往前处理数组
	for i := n / 2; i >= 1; i-- {
		heapifyUpToDown(a, i, n)
	}
}

// 从上往下堆化,top为当前节点
func heapifyUpToDown(a []int, top int, count int) {
	for i := top; i <= count/2; {
		maxIndex := i
		if a[i] < a[i*2] {
			maxIndex = i * 2
		}
		if i*2+1 <= count && a[maxIndex] < a[i*2+1] {
			maxIndex = i*2 + 1
		}
		if maxIndex == i {
			break
		}
		swap(a, i, maxIndex)
		i = maxIndex
	}

}

// 交换数组中两个元素
func swap(a []int, i int, j int) {
	a[i], a[j] = a[j], a[i]
}

func main() {
	//下标从1开始的数组,方便构建堆
	arr := []int{0, 8, 12, 3, 7, 19, 20, 6, 5}
	HeapSort(arr)
	fmt.Println(arr) //[0 3 5 6 7 8 12 19 20]
}
